# 种花问题： https://leetcode-cn.com/problems/can-place-flowers/

# 模拟思路来写： 因为规则保证 010 这样的顺序，当确定1时，身边的两个位置必定为0
class Solution:
    def canPlaceFlowers(self, flowerbed, n):
        i = 0
        # 循环结束条件： 遍历结束和 n大于0
        while (i < len(flowerbed) and n > 0):
            if flowerbed[i] == 1:
                # 根据规则，如果是1，那么它相邻的一定是0，跳过两个位置，才能判断是否能种花       
                i += 2
            else:
                # 当 i 是最后一个花坛为 0时，可以种。 当i+1 == 0 时可以种， 因为根据if的跳转， i-1 一定是 0
                if i == len(flowerbed)-1 or flowerbed[i+1] == 0:
                    n -= 1
                    i += 2 
                # 当 i+1 是1时，那就得跳过三个 
                else:
                    i += 3
        
        return n <= 0


# 官方解答
class Solution:
    def canPlaceFlowers(self, flowerbed, n):
        count, m, prev = 0, len(flowerbed), -1
        for i in range(m):
            if flowerbed[i] == 1:
                if prev < 0:
                    count += i // 2
                else:
                    count += (i - prev - 2) // 2
                if count >= n:
                    return True
                prev = i
        
        if prev < 0:
            count += (m + 1) // 2
        else:
            count += (m - prev - 1) // 2
        
        return count >= n

nums = [1,1,0,0,1]
n = 1

s = Solution()
print(s.canPlaceFlowers(nums, n))